package com.lizk.tree;

/**
 * @author lizhikui
 * @date 2020/2/10 11:20
 */
public class BinarySearch {

    /**
     * 二分查找，在有序的数组中，查找一个指定的值
     * 思路：
     * 1.查看数组中间位置的值是否是要查找的值，如果是，直接返回
     * 2.比较大小，如果中间位置的值比要查找的值大，那么继续用步骤1中的方式搜索中间位置之前的数据，反之亦然。
     * 3.重复1、2两个步骤，直到找到元素，或者没有元素可以拆分数组
     * @param array     有序数组
     * @param target    查找的指定值
     * @return          指定值的索引，没有找到的时候，返回-1
     */
    public static int search(int [] array,int target){
        int begin = 0;
        int end = array.length -1;

        while (begin <= end){
            //这种写法极端情况下会出现超出数据范围的问题
            //int mid = begin + end / 2;
            int mid = begin + (end - begin) / 2;
            if (target == array[mid]){
                return mid;
            }else if (target < array[mid]){
                end = mid - 1;
            }else if(target > array[mid]){
                begin = mid + 1;
            }
        }
        return -1;
    }
}
